// 题目要求：
// 合并 k 个升序链表

// 解题思路：
// 1. 两两合并，直到合并完最后一个：
//    第 0 个链表和第 1 个链表合并，合并完再和第 2 个链表合并，依此类推
//    直到合并完最后一个

// 2. 小根堆
//    将所有头节点都存放在小根堆中
//    拿到最小的头节点，尾插在新链表中
//    如果这个最小的节点后面还有节点，就把后面的节点放到小根堆中
//    重复上述两步，直到小根堆为空

// 3. 归并的思路
// 要合并 [0, n - 1] 区间的链表
// 先计算区间中点 mid = (begin + end) / 2，分别合并 [begin, mid] 和 [mid + 1， end] 区间的链表
// 递归上述步骤，直到 begin > end，返回 null，begin = end，返回 lists.get(begin)
// 返回合并完的链表头节点

import java.util.*;

public class MergeKLinkedList {
    // 解法 1：归并排序 最为重要
    public ListNode mergeKLists1 (ArrayList<ListNode> lists) {
        int n = lists.size();

        return merge(lists, 0, n - 1);
    }

    public ListNode merge(ArrayList<ListNode> lists, int begin, int end){
        if(begin > end) return null;
        if(begin == end) return lists.get(begin);

        int mid = (begin + end) / 2;

        ListNode left = merge(lists, begin, mid);
        ListNode right = merge(lists, mid + 1, end);

        return mergeTwoList(left, right);
    }

    public ListNode mergeTwoList(ListNode node1, ListNode node2){
        ListNode cur1 = node1;
        ListNode cur2 = node2;
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;

        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
            }else{
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }

        if(cur1 != null) cur.next = cur1;
        if(cur2 != null) cur.next = cur2;

        return newHead.next;
    }

    // 解法 2：小根堆
    public ListNode mergeKLists2 (ArrayList<ListNode> lists) {
        int n = lists.size();
        if(n == 0) return null;

        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);

        for(int i = 0; i < n; i++){
            if(lists.get(i) != null){
                heap.offer(lists.get(i));
            }
        }

        ListNode ret = new ListNode(0);
        ListNode cur = ret;

        while(!heap.isEmpty()){
            ListNode t = heap.poll();
            cur.next = t;
            cur = cur.next;
            if(t.next != null){
                heap.offer(t.next);
            }
        }

        return ret.next;
    }

    // 解法 3：两两合并
    public ListNode mergeKLists3 (ArrayList<ListNode> lists) {
        int n = lists.size();
        if(n == 0) return null;
        if(n == 1) return lists.get(0);

        ListNode ret = lists.get(0);
        for(int i = 1; i < n; i++){
            ret = mergeTwoList(ret, lists.get(i));
        }

        return ret;
    }
}
